package mo.offer_special;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class L061 {

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>((e1, e2) -> (e1.get(0)+e1.get(1)-e2.get(0)-e2.get(1)));
        int k1 = Math.min(k, nums1.length);
        int k2 = Math.min(k, nums2.length);
        for (int i = 0; i < k1; i++) {
            for (int j = 0; j < k2; j++) {
                queue.add(Arrays.asList(nums1[i], nums2[j]));
            }
        }
        int idx = 0;
        List<List<Integer>> res = new ArrayList<>();
        while (idx < k && !queue.isEmpty()) {
            res.add(queue.poll());
            idx++;
        }
        return res;
    }

}
